As networked computers and databases, and users of these systems, have proliferated in numbers and geographic spread, interest has grown in efficiently providing access to information objects and services (hereinafter "objects") at host computers or information servers. Presently, for example, thousands of Internet servers provide a very large number of objects to millions of user clients worldwide. These servers are located in many countries around the world and typically at many locations in each country. In other particular cases, network service providers and private corporations locate server nodes at widely separated points in their networks.
A particular challenge faced by developers of these networks of servers is that of providing access to a widely distributed set of clients without overloading particular hosts. The overload may occur, e.g., because a server stores objects that are in high demand and/or the server is a repository for large numbers of objects. Meeting this challenge proves especially difficult when the demand for particular objects varies considerably with time. Thus, while a straightforward replication of all objects at all servers would generally improve availability of a particular object to a range of clients, the cost of such replication is prohibitive. In fact, the economics of replication, distribution and storage do not usually permit design for a worst-case predicted demand condition in such large networks.
The load on each server is an important consideration in adequately meeting demand from clients for objects; in general, it is desirable to balance the load among servers. In many existing replicated object systems, with relatively few servers, this question is quite tractable: system administrators or a dedicated computer system process can monitor the load of servers and decide on selective replica placement. When the number of servers increases, however, such human or dedicated process cannot be expected to efficiently direct the creation and deletion of replicas.
Current object-location techniques used in distributed server networks assume that sets of object replicas are well known to clients. However, when the number and geographic distribution of servers increases to dense national and international proportions this assumption proves unrealistic; the ability of clients to efficiently locate desired objects at servers increases markedly.
One possible solution to the scalability problem of the replication service would be to use a localized "greedy" approach. For example, each hosting server might choose another hosting server at random, and perform load comparisons with this other server. If the load difference exceeds a certain distribution threshold d, the less-loaded server would obtain some replicas of objects kept on the higher-loaded server, thus taking up a portion of its load. Due to the randomness of choice, all pairs of servers would be involved. An approach similar to this is presented in "Adaptive load sharing in homogeneous distributed systems," by T. L. Casavant and J. G. Kuhl, IEEE Trans. on Software Eng., vol. 2(14), pp. 141-154, Feb. 1988. The Casavant, et al paper also defines a threshold for which nodes with a load below the threshold are constrained to not initiate load comparison.
However, as the number of servers grows, each server must initiate load comparison more frequently. Otherwise, the average time between load distribution events for any given pair of nodes will grow linearly with the number of nodes, as will the lag between load changes and detection of these changes. Since a server has a limit on how frequently it can perform load distribution, this solution is not scalable to large systems.
Another approach is to organize hosting servers in a connected graph structure, with neighboring nodes performing pair-wise load distribution. Since the graph is connected the load distribution involves all servers. This technique is similar to an algorithm described in "Simulations of three adaptive, decentralized controlled, job scheduling algorithms," by J. A. Stankovic, Computer Networks, 8, pp. 199-217, August 1984. One difference is that in the Stankovic paper, when a node sends its load data to a neighbor, it includes its information about all other nodes. These techniques also prove to not be scalable as required for large networks.
Another important consideration in establishing a global or other large information system is that of a naming service for objects and servers. In general, naming services are used to map a logical name of an object into the physical name of a replica. The main limiting factors for the name service are the number of clients (which determines the number of requests for name resolution), and the number of objects (which determines the size of the name-mapping database). Another factor is the number of requests from hosting servers for updates of name mappings.
Name services are well known in the art, including the Domain Name Service (DNS) used in today's Internet and described, e.g., in P. V. Mockapetris, "Domain Names--Concepts and Facilities," Request for Comments 1034, DDN Network Infromation Center, SRI International, November, 1987. Also used in Internet naming is CCITT (now ITU) Recommendation X.500.
However, mappings between host name and IP address seldom change in the DNS scheme. Rather, DNS is primarily an append-only database that permits the addition of new host name/IP address mappings; current DNS implementations support little or no dynamic mapping of host name to IP address.
Using current DNS naming service techniques to map logical object names to physical replicas, name server responses cached by clients become incorrect much more quickly. Thus, clients must query the name service much more often, greatly increasing the burden on the name service. Weak-consistency schemes for replicating the mapping database such as that described in B. W. Lampson, "Designing a global name service," Proc. of ACM Conf. on Principles of Distributed Systems, pp1-10, 1986 result in many incorrect responses to clients. These incorrect responses result in the use of an incorrect physical name to access an object--with resulting failure and request renewal.
World-Wide-Web (Web) syntax and semantics for object names (URLs) are quite different from those in DNS or X.500. Use of DNS or X.500-compliant symbolic names in networks like the Web would require extensive changes in Web browsers.